package com.vernhe;

import org.w3c.dom.Node;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

public class BinarySearchTree<E> {
    private int size;
    private Node<E> root;
    private Comparator<E> comparetor;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparetor) {
        this.comparetor = comparetor;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    public void add(E element) {
        elementNotNullCheck(element);

        //如果是第一个元素，即根节点为null
        if (root == null) {
            root = new Node<>(element,null);
            size++;
            return;
        }

        //逐个进行比较
        Node<E> node = root;
        Node<E> parent = null;
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            }else if (cmp < 0) {
                node = node.left;
            }else {
                //相等
                node.element = element;
                return;
            }
        }

        //判断是父节点的左边还是右边
        Node<E> newNode = new Node<>(element,parent);
        if (cmp > 0) {
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }

    }

    /**
     * 两个节点进行比较
     * @param e1
     * @param e2
     * @return  0表示相等，> 表示e1大，< 表示e2大
     */
    private int compare(E e1,E e2) {
        /**
         * 这样写的好处就是不用要求保存的对象一定要实现comparable方法，
         * 而是又外部自行决定使用比较器还是实现comparable方法
         */
        //有比较器用比较器
        if (comparetor != null) {
            return comparetor.compare(e1,e2);
        }
        //没有比较器就用实现Comparable的compareTo方法
        return ((Comparable<E>)e1).compareTo(e2);
    }

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    public void remove(E element) {
        remove(node(element));
    }

    /**
     * 根据元素查找节点
     * @param element
     * @return
     */
    private Node<E> node(E element) {
        if (root == null) return null;
        Node<E> node = root;
        while (node != null) {
            int cmp = compare(element,node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0){
                node = node.left;
            } else {
                //找到就返回
                return node;
            }
        }
        //没找到返回空
        return null;
    }

    private void remove(Node<E> node) {
        if (node == null) return;
        size--;

        //判断是否是度为2的节点
        if (node.hasTowChildren()) {
            //得到替代被删除节点的前驱节点或者后继节点
            Node<E> s = successor(node);
            //覆盖被删除节点的值
            node.element = s.element;
            //删除前驱节点，（本方法就是要删除node节点，因为采用的覆盖的方式，所以真正被删除的节点一定是度为1或者0的节点）
            node = s;
        }

        //如果是度为1的节点，replacement必然不为空，度为0则为空
        Node<E> replacement = node.left != null ? node.left : node.right;
        if (replacement != null) {
            //就算node是根节点，即node.parent == null 也适用
            replacement.parent = node.parent;
            //判断是否为根节点
            if (node.parent == null) {
                root = replacement;
            } else if (node == node.parent.left) {
                //修改原先指向被删除元素的指针
                node.parent.left = replacement;
            } else {
                node.parent.right = replacement;
            }
        } else if (node.parent == null) {
            //度为0是根节点的时候
            root = null;
        } else {
            //度为0是叶子节点的时候
            //根据左右两种情况来进行删除
            if (node == node.parent.left) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
        }
    }

    public boolean contains(E element) {
        return node(element) != null;
    }

    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTowChildren() {
            return left != null && right != null;
        }
    }

    /**
     * 得到传入节点的前驱节点(中序遍历时的前一个节点)
     * @param node
     * @return
     */
    private Node<E> predecessor(Node<E> node) {
        if (node == null) return null;

        //如果左子树不为空，则在左子树中查找
        Node<E> left = node.left;
        if (left != null) {
            while (left.right != null) {
                left = left.right;
            }
            return left;
        }

        //如果左子树为空，则向上查找父节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

//        node.parent == null;  return null
//        node == node.parent.right;  return node.parent
        return node.parent;
    }

    /**
     * 得到传入节点的后继节点，与得到前驱节点的方法对称
     * @param node
     * @return
     */
    private Node<E> successor(Node<E> node) {
        if (node == null) return null;

        //如果右子树不为空，则对其进行查找
        Node<E> right = node.right;
        if (right != null) {
            while (right.left != null) {
                right = right.left;
            }
            return right;
        }

        //如果由子树为空，则向上查找父节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

//        node.parent == null;  return null
//        node == node.parent.left;  return node.parent
        return node.parent;
    }

    /**
     * 调试使用，用于查看树的信息
     */
    public void printInfo() {
        levelOrderTraversal();
    }

//    /**
//     * 树的遍历（中序遍历）
//     * @param node
//     */
//    private void p1(Node<E> node) {
//        if (node.left!= null) p1(node.left);
//        System.out.print(node.element + " -> ");
//        if (node.right!= null) p1(node.right);
//    }

    public void preorder(Visitor<E> visitor) {
        if (visitor == null) return;
        preorder(root,visitor);
    }
    /**
     * 前序遍历
     * @param node
     * @param visitor
     */
    private void preorder(Node<E> node,Visitor visitor) {

        visitor.visit(node.element);
        if (node.left!= null) preorder(node.left,visitor);
        if (node.right!= null) preorder(node.right,visitor);
    }

    public void inorder(Visitor<E> visitor) {
        if (visitor == null) return;
        inorder(root,visitor);
    }
    /**
     * 中序遍历
     * @param node
     * @param visitor
     */
    private void inorder(Node<E> node,Visitor visitor) {
        if (node.left!= null) inorder(node.left,visitor);
        visitor.visit(node.element);
        if (node.right!= null) inorder(node.right,visitor);
    }

    public void postorder(Visitor<E> visitor) {
        if (visitor == null) return;
        postorder(root,visitor);
    }
    /**
     * 后序遍历
     * @param node
     * @param visitor
     */
    private void postorder(Node<E> node,Visitor visitor) {
        if (node.left!= null) postorder(node.left,visitor);
        if (node.right!= null) postorder(node.right,visitor);
        visitor.visit(node.element);
    }


    /**
     * 层序遍历
     */
    private void levelOrderTraversal() {
        if (root == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        Node<E> temp = null;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            System.out.println(temp.element);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            //注意，不能用else if
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

    public static interface Visitor<E> {
        void visit(E element);
    }

    /**
     * 层次遍历，对外提供Visitor接口
     * @param visotor
     */
    public void levelOrder(Visitor visotor) {
        if (root == null || visotor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        Node<E> temp = null;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            visotor.visit(temp.element);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            //注意，不能用else if
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

    /**
     * 判断是否为完全二叉树
     */
    public boolean isComplete() {
        if (root == null) return false;
        boolean sholdBeLeafNode = false;
        Queue<Node<E>> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null){
                return false;
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                sholdBeLeafNode = true;
            }
        }
        return true;
    }

//    /**
//     * 判断是否为完全二叉树
//     */
//    public boolean isComplete() {
//        if (root == null) return false;
//        boolean sholdBeLeafNode = false;
//        Queue<Node<E>> queue = new LinkedList();
//        queue.offer(root);
//        while (!queue.isEmpty()){
//            Node<E> node = queue.poll();
//            if (sholdBeLeafNode && !node.isLeaf()) return false;
//            if (node.hasTowChildren()) {
//                queue.offer(node.left);
//                queue.offer(node.right);
//            } else if (node.left == null && node.right != null) {
//                return false;
//            } else {
//                //【左边不为空，右边为空】【左右都为空】节点之后的都是叶子节点
//                sholdBeLeafNode = true;
//                if (node.left != null) {
//                    queue.offer(node.left);
//                }
//            }
//        }
//        return true;
//    }

    /**
     * 得到树的高度
     * @return
     */
    public int height() {
        //return height1(root);
        return height2();
    }

    /**
     * 递归得到树的高度
     * @param node
     * @return
     */
    private int height1(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height1(node.left),height1(node.right));
    }

    /**
     * 非递归得到树的高度
     * 层次遍历
     * @return
     */
    private int height2() {
        if (root == null) return 0;

        //记录层数
        int levleSize = 0;
        //记录每一层的节点数量
        int rowSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        Node<E> temp = null;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            //每弹出一个元素，这一行的元素个数减一
            rowSize--;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            //注意，不能用else if
            if (temp.right != null) {
                queue.offer(temp.right);
            }
            //当这一行的元素个数为0的时候，说明当前层已经遍历完，层次加一，并更新下一层的rowSize
            if (rowSize == 0) {
                levleSize++;
                rowSize = queue.size();
            }
        }
        return levleSize;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (root == null) return "";
        return toString(root,sb,"");
    }

    private String toString(Node<E> node,StringBuilder sb,String perfix) {
        if (node.left != null) toString(node.left,sb,perfix + "[L]");
        sb.append(perfix).append("【").append(node.element).append("】").append("\n");
        if (node.right != null) toString(node.right,sb,perfix + "[R]");
        return sb.toString();
    }
}
